package demo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        for(String str : words) {
            map1.put(str, map1.getOrDefault(str, 0) + 1);
        }
        int n = s.length(), k = words[0].length();
        List<Integer> list = new ArrayList<>();
        int count = 0;
        for(int x = 0; x<k; x++) {
            for(int i = x, j = x; j < n - k; j += k) {
                String str = s.substring(j, j + k);
                System.out.println(str);
                if(map1.containsKey(str)) {
                    map2.put(str, map2.getOrDefault(str, 0) + 1);
                    while(map2.get(str).compareTo(map1.get(str)) > 0) {
                        String t = s.substring(i, i + k);
                        map2.put(t, map2.get(t) -1);
                        if(map2.get(t) == 0) map2.remove(t);
                        i += k;
                    }
                    if(map2.get(str).equals(map1.get(str))) {
                        count++;
                    }
                    if(count == map1.size()) {
                        list.add(i);
                        String t = s.substring(i, i + k);
                        map2.put(t, map2.get(t) -1);
                        if(map2.get(t) == 0) map2.remove(t);
                        i += k;
                    }
                }else {
                    map2 = new HashMap<>();
                    count = 0;
                    i = j;
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "barfoofoobarthefoobarman";
        String[] words = {"bar","foo","the"};
        solution.findSubstring(s, words);
    }
}